package leetcode_day._2022._202203._1120;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/16 21:37
 * 全 O(1) 的数据结构
 * 算法：哈希表 + 双向链表
 * 以个数大小排列双向链表
 */
public class _16_432 {
    class AllOne {
        class Node {
            int cnt;
            Set<String> set = new HashSet<>();
            Node l, r;
            Node (int _cnt) {
                cnt = _cnt;
            }
        }
        Node head, tail;
        Map<String, Node> map;
        public AllOne() {
            head = new Node(-1);
            tail = new Node(-1);
            head.r = tail;
            tail.l = head;
            map = new HashMap<>();
        }

        public void inc(String key) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.set.remove(key);
                int cnt = node.cnt;
                Node next;
                if (node.r.cnt == cnt + 1) next = node.r;
                else {
                    next = new Node(cnt + 1);
                    next.l = node;
                    next.r = node.r;
                    node.r.l = next;
                    node.r = next;
                }
                clear(node);
                next.set.add(key);
                map.put(key, next);
            } else {
                Node node;
                if (head.r.cnt == 1) node = head.r;
                else {
                    node = new Node(1);
                    node.l = head;
                    node.r = head.r;
                    head.r.l = node;
                    head.r = node;
                }
                node.set.add(key);
                map.put(key, node);
            }
        }

        public void dec(String key) {
            Node node = map.get(key);
            int cnt = node.cnt;
            if (cnt == 1) {
                node.set.remove(key);
                map.remove(key);
            }
            else {
                Node pre;
                if (node.r.cnt == cnt - 1) pre = node.l;
                else {
                    pre = new Node(cnt - 1);
                    pre.l = node;
                    pre.r = node.r;
                    node.r.l = pre;
                    node.r = pre;
                }
                pre.set.add(key);
                map.put(key, pre);
            }
            clear(node);
        }

        public String getMaxKey() {
            if (tail.l != head) for (String s : tail.l.set) return s;
            return "";
        }

        public String getMinKey() {
            if (head.r != tail) for (String s : head.r.set) return s;
            return "";
        }

        public void clear(Node node) {
            if (node.set.size() == 0) {
                Node left = node.l;
                left.r = node.r;
                node.r.l = left;
            }
        }
    }
}
